{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Largest Sum of Averages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: largestSumOfAverages"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大平均值和的分组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;。我们将给定的数组&nbsp;<code>nums</code>&nbsp;分成 <strong>最多</strong>&nbsp;<code>k</code>&nbsp;个非空子数组，且数组内部是连续的&nbsp;。&nbsp;<strong>分数</strong> 由每个子数组内的平均值的总和构成。</p>\n",
    "\n",
    "<p>注意我们必须使用 <code>nums</code> 数组中的每一个数进行分组，并且分数不一定需要是整数。</p>\n",
    "\n",
    "<p>返回我们所能得到的最大 <strong>分数</strong> 是多少。答案误差在&nbsp;<code>10<sup>-6</sup></code>&nbsp;内被视为是正确的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [9,1,2,3,9], k = 3\n",
    "<strong>输出:</strong> 20.00000\n",
    "<strong>解释:</strong> \n",
    "nums 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20. \n",
    "我们也可以把 nums 分成[9, 1], [2], [3, 9]. \n",
    "这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,2,3,4,5,6,7], k = 4\n",
    "<strong>输出:</strong> 20.50000\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [largest-sum-of-averages](https://leetcode.cn/problems/largest-sum-of-averages/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [largest-sum-of-averages](https://leetcode.cn/problems/largest-sum-of-averages/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,1,2,3,9]\\n3', '[1,2,3,4,5,6,7]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        dp = [0] * (n + 1)\n",
    "        sums = [0]\n",
    "        for i in range(1, n + 1):\n",
    "            sums.append(sum(nums[:i]))\n",
    "            dp[i] = sum(nums[:i]) / i\n",
    "        for j in range(2, k + 1):\n",
    "            for i in range(n, j - 1, -1):\n",
    "                for x in range(j - 1, i):\n",
    "                    dp[i] = max(dp[i], dp[x] + (sums[i] - sums[x]) / (i - x))\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        from itertools import accumulate\n",
    "        n = len(nums)\n",
    "        sums = list(accumulate(nums))\n",
    "        dp = [[0]*k for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][0] = sums[i]/1.0/(i+1)\n",
    "            for q in range(i):\n",
    "                for j in range(1,k):\n",
    "                    dp[i][j] = max(dp[q][j-1]+(sums[i]-sums[q])/1.0/(i-q),dp[i][j])\n",
    "        #print(dp)\n",
    "        return dp[-1][-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], m: int) -> float:\n",
    "        n = len(nums)\n",
    "        psum = [0] * (n + 10)\n",
    "        for i in range(1, n + 1): ### 前缀和\n",
    "            psum[i] = psum[i - 1] + nums[i - 1]\n",
    "        f = [[0] * (m + 10) for _ in range(n + 10)]\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, min(i, m) + 1):\n",
    "                if j == 1:\n",
    "                    f[i][j] = psum[i] / i\n",
    "                else:\n",
    "                    for k in range(2, i + 1):\n",
    "                        f[i][j] = max(f[i][j], f[k - 1][j - 1] + (psum[i] - psum[k - 1]) / (i - k + 1))\n",
    "        return f[n][m]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n=len(nums)\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            pre[i]=pre[i-1]+nums[i-1]\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            if i==0:\n",
    "                return pre[j+1]/(j+1)\n",
    "            res=0\n",
    "            for l in range(i,j+1):\n",
    "                res=max(res,dfs(i-1,l-1)+(pre[j+1]-pre[l])/(j-l+1))\n",
    "            return res\n",
    "        return dfs(k-1,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "\n",
    "        n = len(nums)\n",
    "        perfix = list(accumulate(nums,initial=0))\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int,j :int)->float:\n",
    "\n",
    "            if j == 1:\n",
    "                return perfix[i+1]/(i+1)\n",
    "            ans =  0\n",
    "            for L in range(j-1,i+1):\n",
    "                ans = max(ans,dfs(L-1,j-1)+(perfix[i+1]-perfix[L])/(i-L+1))\n",
    "            return ans\n",
    "\n",
    "\n",
    "        return dfs(n-1,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        # 记忆搜索的dfs\n",
    "        n = len(nums)\n",
    "        preSum, s = [0], 0\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            preSum.append(s)\n",
    "        @cache\n",
    "        def dfs(i, curK): # 从i开始最多分成K组的最大平均值和\n",
    "            if i == n: # 遍历到末尾\n",
    "                return 0\n",
    "            if curK == 1: # 只剩下当前这组，不需要分割\n",
    "                return (preSum[-1] - preSum[i]) / (n - i)\n",
    "            ans = 0\n",
    "            for j in range(i+1, n): # 枚举从[i+1,n-1]位置进行分割\n",
    "                ans = max(ans, (preSum[j] - preSum[i]) / (j - i) + dfs(j, curK - 1))\n",
    "            return ans\n",
    "        return dfs(0, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n=len(nums)\n",
    "        pre=list(accumulate(nums,initial=0))\n",
    "        def get_mean(l,r):\n",
    "            l,r=l+1,r+1\n",
    "            return (pre[r]-pre[l-1])/(r-l+1)\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx,left):\n",
    "            if left==1:\n",
    "                return get_mean(idx,n-1)\n",
    "            ans=-inf\n",
    "            for i in range(idx,n-1):\n",
    "                ans=max(ans,get_mean(idx,i)+dfs(i+1,left-1))\n",
    "            return ans\n",
    "        return dfs(0,k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "\n",
    "        recursion_dict = {}\n",
    "        def dfs(nums, i, k):\n",
    "            if k == 1:\n",
    "                return sum(nums[i:])/len(nums[i:])\n",
    "            if k > len(nums):\n",
    "                return dfs(nums, i, len(nums))\n",
    "            result = float('-inf')\n",
    "            if (i, k) in recursion_dict:\n",
    "                return recursion_dict[(i, k)]\n",
    "            for t in range(i+1, len(nums)):\n",
    "                tmp = nums[i:t]\n",
    "                r = dfs(nums, t, k-1)\n",
    "                print(i,t, r)\n",
    "                if sum(tmp)/len(tmp) + r > result:\n",
    "                    result = sum(tmp)/len(tmp) + r\n",
    "            recursion_dict[(i, k)] = result\n",
    "            return result\n",
    "        return dfs(nums, 0, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        dct = {}\n",
    "        \n",
    "        @lru_cache\n",
    "        def dfs(A: tuple, n: int) -> float:\n",
    "            if (A, n) in dct:\n",
    "                return dct[(A, n)]\n",
    "            if n > len(A):\n",
    "                return -1\n",
    "            if n == 1:\n",
    "                dct[(A, n)] = sum(A)/len(A)\n",
    "                return dct[(A, n)]\n",
    "            dct[(A, n)] = max(sum(A[:i])/i+dfs(A[i:], n-1) for i in range(1, len(A)+1))\n",
    "            return dct[(A, n)]\n",
    "        \n",
    "        return dfs(tuple(A), K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        @cache\n",
    "        def dfs(i, cnt):\n",
    "            if i == len(nums) and cnt <= k:\n",
    "                return 0.0\n",
    "            ret = -inf\n",
    "            for j in range(i+1, len(nums)+1):\n",
    "                ret = max(ret, dfs(j, cnt+1) + sum(nums[i:j]) / (j - i))\n",
    "            return ret\n",
    "        return dfs(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def dfs(i, j, p):\n",
    "            res = 0\n",
    "            if p == 1:\n",
    "                res = sum(nums[x] for x in range(i,j+1))/(j-i+1)\n",
    "            elif j-i+1 == p:\n",
    "                res = sum(nums[x] for x in range(i,j+1))\n",
    "            else:\n",
    "                for h in range(i, j):\n",
    "                    if j-h < p-1:\n",
    "                        break\n",
    "                    # print('---',i,h,h+1, j)\n",
    "                    res = max(res, dfs(i,h,1) + dfs(h+1,j,p-1))\n",
    "            print(i,j,p, res)\n",
    "            return res\n",
    "        return dfs(0, n-1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        d=dict()\n",
    "        def fn(nums,k):\n",
    "            if k>len(nums):return 0\n",
    "            if (tuple(nums),k) in d:\n",
    "                return d[(tuple(nums),k)]\n",
    "            if len(nums)==0:return 0\n",
    "            if k==1:return sum(nums)/len(nums)\n",
    "            ms=0\n",
    "            for i in range(len(nums)):\n",
    "                t=sum(nums[:i+1])/(i+1)\n",
    "                if k-1>=1:\n",
    "                    r=fn(nums[i+1:],k-1)\n",
    "                ms=max(ms,t+r)\n",
    "            d[(tuple(nums),k)]=ms\n",
    "            return ms\n",
    "        return fn(nums,k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        tmp=[]\n",
    "        tmpsum=0\n",
    "        for i in range(len(nums)):\n",
    "            tmpsum+=nums[i]\n",
    "            tmp.append(tmpsum)\n",
    "        @cache\n",
    "        def getmean(i,j):\n",
    "            if i==0:\n",
    "                return tmp[j]/(j+1)\n",
    "            return (tmp[j]-tmp[i-1])/(j-i+1)\n",
    "        #while len(ans)<k:\n",
    "        #    ans.append([0 for _ in range(len(nums))])\n",
    "        #    tmpk=len(ans)\n",
    "        #    tmpsum=0\n",
    "        #    for idx in range(len(nums)-1,tmpk-2,-1):\n",
    "        #        tmpsum+=nums[idx]\n",
    "        #        ans[-1][idx]=\n",
    "        @cache\n",
    "        def getans(idx,k):\n",
    "            #0->idx分成k组的结果\n",
    "            if k==idx+1:\n",
    "                return tmp[idx]\n",
    "            if k==1:\n",
    "                return tmp[idx]/(idx+1)\n",
    "\n",
    "            \n",
    "            ans=0\n",
    "            for i in range(k-2,idx):\n",
    "                ans=max(ans,getans(i,k-1)+getmean(i+1,idx))\n",
    "            return ans\n",
    "        return getans(len(nums)-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        @cache \n",
    "        def f(i,j,k): #nums[i,j)分为k组\n",
    "            if j - i <= k : return sum(nums[i:j])\n",
    "            if k == 1: return sum(nums[i:j]) / (j-i)\n",
    "            return max(\n",
    "                f(i,m,k-1)+f(m,j,1) for m in range(i+k-1,j)\n",
    "            )\n",
    "        return f(0,len(nums),k)\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        @cache \n",
    "        def f(i,j,k): #nums[i,j)分为k组\n",
    "            if j - i <= k : return sum(nums[i:j])\n",
    "            if k == 1: return sum(nums[i:j]) / (j-i)\n",
    "            if i : return 0 \n",
    "            return max(\n",
    "                f(i,m,k-1)+f(m,j,1) for m in range(i+k-1,j)\n",
    "            )\n",
    "        return f(0,len(nums),k)\n",
    "\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1) \n",
    "        for i in range(1, n + 1): \n",
    "            s[i] = s[i - 1] + nums[i - 1]\n",
    "\n",
    "        @cache\n",
    "        def dp(i, j, k): \n",
    "            if j - i + 1 < k: return s[j + 1] - s[i]\n",
    "            if k == 1: return (s[j + 1] - s[i]) / (j - i + 1) \n",
    "            res = -inf\n",
    "            for t in range(i, j): \n",
    "                res = max(res, dp(i, t, k - 1) + dp(t + 1, j, 1))\n",
    "            return res \n",
    "        \n",
    "        return dp(0, n - 1, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# [9,1,2,3,9]\n",
    "# k = 3\n",
    "# >> 20\n",
    "# [1,2,3,4,5,6,7], k = 4\n",
    "# k = 4\n",
    "# >> 20.5\n",
    "\n",
    "# 动态规划\n",
    "\n",
    "\n",
    "# 递归+记忆化（超时）\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        @cache\n",
    "        def sub(i: int, j: int, k: int) -> float:\n",
    "            d = j - i\n",
    "            if k == 0 or k > d:\n",
    "                return float('-inf') # 表示已无意义\n",
    "            if k == d:\n",
    "                return sum(nums[i:j])\n",
    "            if k == 1:\n",
    "                return sum(nums[i:j]) / d\n",
    "            return max(sub(i, m, 1) + sub(m, j, k-1) for m in range(i+1, j))\n",
    "        return sub(0, len(nums), k)\n",
    "\n",
    "# 递归（超时）\n",
    "# class Solution:\n",
    "#     def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "#         def sub(nums: List[int], k: int) -> float:\n",
    "#             if k == 0 or k > len(nums):\n",
    "#                 return float('-inf') # 表示已无意义\n",
    "#             if k == len(nums):\n",
    "#                 return sum(nums)\n",
    "#             if k == 1:\n",
    "#                 return sum(nums) / len(nums)\n",
    "#             return max(sub(nums[:i], 1) + sub(nums[i:], k-1) for i in range(1, len(nums)))\n",
    "#         return sub(nums, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        from functools import cache\n",
    "\n",
    "        # pre_sum(i) the pre-sum at index i\n",
    "        @cache\n",
    "        def pre_sum(i):\n",
    "            if i < 0:\n",
    "                return 0\n",
    "            return nums[i] + pre_sum(i - 1)\n",
    "\n",
    "        # avg(i, j) the average of nums[i:j + 1]\n",
    "        @cache\n",
    "        def avg(i, j):\n",
    "            return (pre_sum(j) - pre_sum(i) + nums[i]) / (j - i + 1)\n",
    "\n",
    "        # dp(i, j): max sum of at most j averages from first i elements\n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if j == 1:\n",
    "                return avg(0, i - 1)\n",
    "            return max(dp(m, j - 1) + avg(m, i - 1) for m in range(i))\n",
    "\n",
    "        return dp(len(nums), k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n=len(nums)\n",
    "        pre=list(accumulate(nums,initial=0))\n",
    "        @lru_cache(None)\n",
    "        def get_mean(l,r):\n",
    "            l,r=l+1,r+1\n",
    "            return (pre[r]-pre[l-1])/(r-l+1)\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx,left):\n",
    "            if left==1:\n",
    "                return get_mean(idx,n-1)\n",
    "            ans=-inf\n",
    "            for i in range(idx,n-1):\n",
    "                ans=max(ans,get_mean(idx,i)+dfs(i+1,left-1))\n",
    "            return ans\n",
    "        return dfs(0,k)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i,j,k):\n",
    "            if i > j:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                return sum(nums[x] for x in range(i,j+1)) / (j-i+1)\n",
    "            res = 0\n",
    "            for x in range(i,j+1):\n",
    "                res = max(dfs(i,x,1) + dfs(x+1,j,k-1),res)\n",
    "            return res\n",
    "        return dfs(0,n-1,k)\n",
    "            \n",
    "        # dp = [[[0 for _ in range(k+1)] for _ in range(n)] for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     dp[i][i][1] = nums[i]\n",
    "        #     for j in range(i+1,n):\n",
    "        #         dp[i][j][1] = (dp[i][j-1][1] * (j-i) + nums[j]) / (j-i+1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "\n",
    "        result = self.func(tuple(nums),k)\n",
    "        return result\n",
    "\n",
    "    \n",
    "    @lru_cache(None)\n",
    "    def func(self,nums,k):\n",
    "        if len(nums)<k:\n",
    "            return 0\n",
    "        if k==1:\n",
    "            return sum(nums)/len(nums)\n",
    "\n",
    "        cur_result = 0\n",
    "        tmp_sum = 0\n",
    "        for i in range(len(nums)-k+1):\n",
    "            tmp_sum+=nums[i]\n",
    "            sub_result = self.func(tuple(nums[i+1:]),k-1)\n",
    "            cur_tmp = tmp_sum/(i+1) + sub_result\n",
    "            cur_result = max(cur_result,cur_tmp)\n",
    "        return cur_result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1) \n",
    "        for i in range(1, n + 1): \n",
    "            s[i] = s[i - 1] + nums[i - 1]\n",
    "\n",
    "        @cache\n",
    "        def dp(i, j, k): \n",
    "            if j - i + 1 < k: return 0 \n",
    "            if k == 1: return (s[j + 1] - s[i]) / (j - i + 1) \n",
    "            res = -inf\n",
    "            for t in range(i, j): \n",
    "                res = max(res, dp(i, t, k - 1) + dp(t + 1, j, 1))\n",
    "            return res \n",
    "        \n",
    "        return max(dp(0, n - 1, t) for t in range(1, k + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        if k==1: return sum(nums)/n\n",
    "        dp = [[],[]]  # k_len * start * \n",
    "        for s in range(n):\n",
    "            dp[-1].append([nums[s]])\n",
    "            for e in range(s+1,n):\n",
    "                l = e-s+1\n",
    "                dp[-1][-1].append((nums[e]+dp[-1][-1][-1]*(l-1))/l)\n",
    "        # print(dp)\n",
    "        tma = 0\n",
    "        for l in range(2,k+1): # len\n",
    "            dp.append([])\n",
    "            for s in range(n):\n",
    "                dp[-1].append([])\n",
    "                for e in range(s+l-1,n):\n",
    "                    # print(l,s,e)\n",
    "                    # e-sp>=l-1 -> sp<=e-l+1\n",
    "                    # ma = 0\n",
    "                    ma = max(dp[1][s][sp-s]+dp[l-1][sp+1][e-sp-l+1] for sp in range(s,e-l+2))\n",
    "                    # for sp in range(s,e-l+2):\n",
    "                    #     print(l,s,e,sp)\n",
    "                    #     # sp+l-1 == e\n",
    "                    #     ma = max(ma,dp[1][s][sp-s]+dp[l-1][sp+1][e-sp-l+1])\n",
    "                    dp[-1][-1].append(ma)\n",
    "                    # tma = max(tma,ma)\n",
    "            # print(dp[-1])\n",
    "        # print(dp[1])\n",
    "        # print(dp[2])\n",
    "        # print(dp[-1])\n",
    "        return dp[-1][0][-1]\n",
    "        # return max(dp[-1][0])\n",
    "        # return dp[-1][-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n = len(nums)\n",
    "        if k==1: return sum(nums)/n\n",
    "        dp = [[],[]]  # k_len * start * \n",
    "        for s in range(n):\n",
    "            dp[-1].append([nums[s]])\n",
    "            for e in range(s+1,n):\n",
    "                l = e-s+1\n",
    "                dp[-1][-1].append((nums[e]+dp[-1][-1][-1]*(l-1))/l)\n",
    "        # print(dp)\n",
    "        tma = 0\n",
    "        for l in range(2,k+1): # len\n",
    "            dp.append([])\n",
    "            for s in range(n):\n",
    "                dp[-1].append([])\n",
    "                for e in range(s+l-1,n):\n",
    "                    ma = max(dp[1][s][sp-s]+dp[l-1][sp+1][e-sp-l+1] for sp in range(s,e-l+2))\n",
    "                    dp[-1][-1].append(ma)\n",
    "        return dp[-1][0][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        dp = [[[-1]*len(A) for i in range(0,len(A))]for j in range(0,K+1)]   #dp[i][j][k]代表假设第i个分组从第j个下标开始到第k个下标结束，当前所有分组的平均值的和，是当前遍历到的所有分组\n",
    "        ans = -2\n",
    "        qianzhuiSum = [A[0]]  #前缀和数组，方便求当前分组的数字值的总和\n",
    "        for i in range(1,len(A)):\n",
    "            qianzhuiSum.append(qianzhuiSum[i-1] + A[i])\n",
    "        for i in range(1,K+1):\n",
    "            for st in range(0+i-1,len(A)-(K-i)):  #  考虑到能都形成指定数量的分组，要对开始下标与结束下标加以限制  假设K==2,那个第2个分组开始下标不能小于1，否则无法划分出第一个分组\n",
    "                for en in range(st,len(A)-(K-i)):  # 假设K==2,那么第1个分组结束下标不能大于len(A)-2，否则无法划分出第二个分组\n",
    "                    if(i==K and en != len(A)-1):  #最后我们要判断出dp[K][x][len(A)-1]的最大值，所以当i==K时，我们只计算en == len(A)-1的情况即可，其他情况对于结果派不上用场\n",
    "                        continue\n",
    "                    if(i>1):\n",
    "                        dp[i][st][en] = (qianzhuiSum[en] - qianzhuiSum[st-1])/(en-st+1)  #计算出当前分组的平均值\n",
    "                        tmp = max([dp[i-1][o][st-1] for o in range(i-2,st)])  #求出当前分组的位置确定的情况下，前面所有数据的平均值的和\n",
    "                        dp[i][st][en] += tmp    #前面所有分组平均值的和+当前分组平均值的和 得出当前所有分组平均值的和\n",
    "                    else:\n",
    "                        dp[i][st][en] = (qianzhuiSum[en])/(en+1)   #如果当前是第一个分组，计算平均值很简单\n",
    "                    if(i == K and en == (len(A)-1) and dp[i][st][en] > ans):   #当计算到dp[K][x][len(A)-1]的情况时，在此处记录下最大值，如果不在此处记录，之后也要循环一遍dp[K][x][len(A)-1]，得出最大值\n",
    "                        ans = dp[i][st][en]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        curtarget = 1\n",
    "        dp = [[[-1]*len(A) for i in range(0,len(A))]for j in range(0,K+1)]\n",
    "        ans = -2\n",
    "        qianzhuiSum = [A[0]]\n",
    "        for i in range(1,len(A)):\n",
    "            qianzhuiSum.append(qianzhuiSum[i-1] + A[i])\n",
    "        maxdp = [[-1 for j in range(0,len(A))] for i in range(1,K+1)]\n",
    "        for i in range(1,K+1):\n",
    "            for st in range(0+i-1,len(A)-(K-i)):\n",
    "                for en in range(st,len(A)-(K-i)):\n",
    "                    if(i==K and en != len(A)-1):\n",
    "                        continue\n",
    "                    if(i>1): \n",
    "                        dp[i][st][en] = (qianzhuiSum[en] - qianzhuiSum[st-1])/(en-st+1)            \n",
    "                        if(maxdp[i-1][st-1] == -1):\n",
    "                            for q in range(i-2,st):\n",
    "                                if(dp[i-1][q][st-1] > maxdp[i-1][st-1]):\n",
    "                                    maxdp[i-1][st-1] = dp[i-1][q][st-1]    \n",
    "                        dp[i][st][en] += maxdp[i-1][st-1]        \n",
    "                    else:\n",
    "                        dp[i][st][en] = (qianzhuiSum[en])/(en+1)\n",
    "                    if(i == K and en == (len(A)-1) and dp[i][st][en] > ans):\n",
    "                        ans = dp[i][st][en]\n",
    "        return ans   \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k2: int) -> float:\n",
    "        \"\"\"\n",
    "\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        pass\n",
    "        cache = 0\n",
    "        dp = {}\n",
    "        dp[-1] = 0\n",
    "        for k, v in enumerate(nums):\n",
    "            cache += v\n",
    "            dp[k] = cache\n",
    "        self.dp = dp\n",
    "        return self.getAns(0, len(nums) - 1, k2)\n",
    "\n",
    "    @lru_cache(None)\n",
    "    def getAns(self, l, r, k2):\n",
    "        if k2 == 0:\n",
    "            return 0\n",
    "        if k2 == 1:\n",
    "            sum1 = self.dp[r] - self.dp[l - 1]\n",
    "            len1 = r - l + 1\n",
    "            return sum1 / len1\n",
    "        ok = 0\n",
    "        for i in range(l, r):\n",
    "            ok = max(ok, self.getAns(l, i, 1) + self.getAns(i + 1, r, k2 - 1))\n",
    "        return ok\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.largestSumOfAverages(nums=[1, 1, 4], k2=2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n=len(nums)\n",
    "        dp=[[[None]*n for _ in range(n)] for _ in range(k)]\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                dp[0][i][j]=sum(nums[i:j+1])/(j-i+1)\n",
    "        # print(dp[0])\n",
    "        for i in range(1,k):\n",
    "            for p in range(n-i):\n",
    "                for q in range(p+i,n):\n",
    "                    dp[i][p][q]=0.0\n",
    "                    for l in range(p,q-i+1):\n",
    "                        dp[i][p][q]=max(dp[i][p][q],dp[0][p][l]+dp[i-1][l+1][q])\n",
    "            # print(dp[i])\n",
    "\n",
    "\n",
    "        return dp[k-1][0][n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        \"\"\"\n",
    "        以 [9, 1, 2, 3, 9] 为例，我们发现上述的解法重复计算了 k 为 1 的很多结果\n",
    "        比如将已知 k 为 1 的情况即为 △\n",
    "        res = max(△+F(1,4,2), △+F(2,4,2), △+F(3,4,2))\n",
    "        F(1,4,2)=max(△+F(2,4,1), △+F(3,4,1), △+F(4,4,1))\n",
    "        F(2,4,2)=max(△+F(3,4,1), △+F(4,4,1))\n",
    "        F(3,4,2)=△\n",
    "        再来看一下为什么没写 △+F(4,4,2) 即 F(0,3,1)+F(4,4,2)\n",
    "        因为在其他情况中已经包含了：\n",
    "        F(0,0,1)+F(1,3,1)+F(4,4,1)\n",
    "        F(0,1,1)+F(2,3,1)+F(4,4,1)\n",
    "        (a+b+c+d)/4 势必比 a+(b+c+d)/3 (a+b)/2+(c+d)/2 要小，所以可以不予计算\n",
    "        所以我们用一个三维数组来存储问题的答案\n",
    "        z=1 和 y-x+1=z 的情况结果已知\n",
    "        :param nums:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        summary = [0]\n",
    "        for i in range(length):\n",
    "            summary.append(summary[-1] + nums[i])\n",
    "        dp = [[[0] * (k + 1) for _ in range(length)] for _ in range(length)]\n",
    "        for z in range(1, k + 1):\n",
    "            for x in range(length - 1, -1, -1):\n",
    "                if length-x < z:\n",
    "                    continue\n",
    "                if z == 1:\n",
    "                    dp[x][length - 1][1] = (summary[length] - summary[x]) / (length - x)\n",
    "                else:\n",
    "                    tmp = float('-inf')\n",
    "                    for y in range(x + 1, length):\n",
    "                        dp[x][y-1][1] = (summary[y] - summary[x]) / (y-x)\n",
    "                        if length - y < z - 1:\n",
    "                            break\n",
    "                        else:\n",
    "                            tmp = max(tmp, dp[x][y - 1][1] + dp[y][length - 1][z - 1])\n",
    "                    dp[x][length - 1][z] = tmp\n",
    "        return dp[0][length - 1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        s=[0]+list(accumulate(nums))\n",
    "        @cache \n",
    "        def f(i,j,m):\n",
    "            if m == 1 or j-i==1 : return (s[j]-s[i]) / (j-i)\n",
    "            if j-i <= m : return s[j]-s[i]\n",
    "            if m & 1:\n",
    "                return max(\n",
    "                f(i,k,1) + f(k,j,m-1) for k in range(i+1,j)\n",
    "            )\n",
    "            return max(\n",
    "                f(i,k,m//2) + f(k,j,m//2) for k in range(i+1,j))\n",
    "        return f(0,len(nums),k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        mean_func = lambda a: sum(a) * 1.0 / len(a)\n",
    "        n = len(A)\n",
    "        dp_pre = [mean_func(A[:i+1]) for i in range(n)]\n",
    "        dp_cur = dp_pre[:]\n",
    "        k = 1\n",
    "        while k < K:\n",
    "            k += 1\n",
    "            for i in range(n):\n",
    "                if i+1 < k:\n",
    "                    dp_cur[i] = 0\n",
    "                    continue\n",
    "                if i+1 == k:\n",
    "                    dp_cur[i] = sum(A[:i+1])\n",
    "                    continue\n",
    "\n",
    "                dp_cur[i] = max([dp_pre[j] + mean_func(A[j+1:i+1]) for j in range(i)])\n",
    "            dp_pre = dp_cur[:]\n",
    "        return dp_cur[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        mat = np.zeros([K+1, len(A)+1])\n",
    "        for i in range(1,len(A)+1):\n",
    "            mat[1][i] = np.mean(A[:i])\n",
    "        for k in range(2,K+1):\n",
    "            for i in range(k,len(A)+1):\n",
    "                mat[k][i] = max([mat[k-1][j]+np.mean(A[j:i]) for j in range(k-1, i)])\n",
    "        return mat[K][len(A)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        length = len(A)\n",
    "\n",
    "        if length <= K:\n",
    "            return sum(A)\n",
    "        dp = np.zeros((length,K))\n",
    "        P = [0]\n",
    "        for x in A: P.append(P[-1] + x)\n",
    "        def average(i, j):\n",
    "            return (P[j] - P[i]) / float(j - i)\n",
    "        dp = [average(i, length) for i in range(length)] # 计算只有一组时候的最大值\n",
    "        for _ in range(K-1):\n",
    "            for i in range(length):\n",
    "                for j in range(i+1,length):\n",
    "                    \"\"\"\n",
    "                    就是分成三段[0,i],[i,j],[j,最后] 来算最大值。\n",
    "                    因为第一个总会变大。\n",
    "                    \"\"\"\n",
    "                    dp[i] = max(dp[i], average(i, j) + dp[j]) \n",
    "\n",
    "        return    dp[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        record = {}\n",
    "        \n",
    "        def helper(i,k):\n",
    "            if i <= 0 or k <= 0:\n",
    "                return 0\n",
    "            if k == 1:\n",
    "                record[(i,k)] = sum(A[:i])/i\n",
    "                return record[(i,k)]\n",
    "            if i <= k:\n",
    "                record[(i,k)] = sum(A[:i])\n",
    "                return record[(i,k)]\n",
    "            if (i,k) in record:\n",
    "                return record[(i,k)]\n",
    "            res = helper(i-1,k-1)+A[i-1]\n",
    "            for j in range(2,i+1):\n",
    "                res = max(res,helper(i-j,k-1)+sum(A[i-j:i])/j)\n",
    "            record[(i,k)] = res\n",
    "            return record[(i,k)]\n",
    "        \n",
    "        res = helper(len(A),K)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        n = len(A)\n",
    "        p = [0]\n",
    "        for i in A:\n",
    "            p.append(p[-1]+i)\n",
    "        def avg(i,j):\n",
    "            return (p[j] - p[i])/float(j-i)\n",
    "        dp = [[0.0 for _ in range(n+1)]for _ in range(K+1)]\n",
    "        for i in range(1,n+1):\n",
    "            dp[1][i] = avg(0,i)\n",
    "        for k in range(2,K+1):\n",
    "            for i in range(k,n+1):\n",
    "                for j in range(k-1,i):\n",
    "                    dp[k][i] = max(dp[k][i],dp[k-1][j]+ avg(j,i))\n",
    "        return dp[-1][-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        import numpy as np\n",
    "        \"\"\"\n",
    "        dp[i][k]表示0～i(包括i)元素分成k份能获得的均值总和，则\n",
    "        dp[i][k] = max(dp[j][k-1]+avg(j+1, i)), 0<=j<i\n",
    "        dp[0][k] = A[0] ,表示0号元素拆分为K份的均值，为A[0]/1+0=A[0]\n",
    "        dp[i][1] = avg(0, i),表示把0-i元素分成1份\n",
    "        返回值为dp[n-1][K]\n",
    "        \"\"\"\n",
    "        n = len(A)\n",
    "        dp = [[0] * (K+1) for _ in range(n)]\n",
    "        for k in range(1, K+1):\n",
    "            dp[0][k] = A[0]\n",
    "        for i in range(n):\n",
    "            dp[i][1] = sum(A[:i+1])/(i+1)\n",
    "        for i in range(1, n):\n",
    "            for k in range(2, K+1):\n",
    "                for j in range(i):\n",
    "                    dp[i][k] = max(dp[i][k], dp[j][k - 1] + sum(A[j + 1:i+1]) / (i - j))\n",
    "        return dp[n-1][K]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self._visted = []\n",
    "        self._A = None\n",
    "\n",
    "    def largestSumOfAverages(self, A: List[int], K: int) -> float:\n",
    "        num = len(A)\n",
    "        self._A = A\n",
    "        for _ in range(num):\n",
    "            self._visted.append([-1] * K)\n",
    "        self._search(num-1, K-1)\n",
    "        return self._visted[num-1][K-1]\n",
    "\n",
    "    def _search(self, i, k):\n",
    "        if i < 0 or k < 0:\n",
    "            return 0\n",
    "        if self._visted[i][k] != -1:\n",
    "            return self._visted[i][k]\n",
    "        if k == 0:\n",
    "            self._visted[i][k] = np.sum(self._A[:i + 1]) / (i + 1)\n",
    "            return self._visted[i][k]\n",
    "        if i == k:\n",
    "            self._visted[i][k] = np.sum(self._A[:k+1])\n",
    "            return self._visted[i][k]\n",
    "        sub_sum = 0\n",
    "        sub_len = 0\n",
    "        max_val = 0\n",
    "        max_idx = -1\n",
    "        for j in range(i, k-1, -1):\n",
    "            sub_sum += self._A[j]\n",
    "            sub_len += 1\n",
    "            val = sub_sum / sub_len + self._search(j-1, k-1)\n",
    "            if val > max_val:\n",
    "                max_val = val\n",
    "                max_idx = j\n",
    "        print(k, max_idx, max_val)\n",
    "        self._visted[i][k] = max_val\n",
    "        return self._visted[i][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], kk: int) -> float:\n",
    "        n=len(nums)\n",
    "        dp = [[[0 for _ in range(kk)]for _ in range(n)]for _ in range(n)]\n",
    "        for i in range(0,n):\n",
    "            dp[i][i][0]=nums[i]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for k in range(0,kk):\n",
    "                for j in range(i+k,n):\n",
    "                    if k==0:\n",
    "                        dp[i][j][k]=(dp[i][j-1][k]*(j-i)+nums[j])/(j-i+1)\n",
    "                    else:\n",
    "                        dp[i][j][k]=0\n",
    "                        for l in range(i+k-1,j):\n",
    "                            dp[i][j][k]=max(dp[i][j][k],dp[i][l][k-1]+dp[l+1][j][0])\n",
    "        # for i in range(0,n):\n",
    "        #     for j in range(n):\n",
    "        #         print(dp[i][j][1],end=\" \")\n",
    "        #     print(\" \")\n",
    "        return dp[0][n-1][kk-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# [9,1,2,3,9]\n",
    "# k = 3\n",
    "# >> 20\n",
    "# [1,2,3,4,5,6,7], k = 4\n",
    "# k = 4\n",
    "# >> 20.5\n",
    "\n",
    "# 动态规划\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        N = len(nums)\n",
    "        # 构造dp多维数组\n",
    "        dp = [[[float('-inf')] * (k+1) for j in range(N+1)] for i in range(N+1)]\n",
    "        # 初始化dp基础状态\n",
    "        # dp\n",
    "        for i in range(N, -1, -1):\n",
    "            for j in range(i+1, N+1):\n",
    "            # for j in range(N, i, -1): # 逆序不行\n",
    "                d = j - i\n",
    "                sm = sum(nums[i:j])  # todo memo\n",
    "                dp[i][j][1] = sm / d\n",
    "                # for p in range(2, min(k+1, d+1)):\n",
    "                for p in range(min(k, d), 1, -1):\n",
    "                    if p == d:\n",
    "                        dp[i][j][p] = sm\n",
    "                    dp[i][j][p] = max(dp[i][m][1]+dp[m][j][p-1] for m in range(i+1,j))\n",
    "        return dp[0][N][k]\n",
    "\n",
    "# 递归+记忆化（超时）\n",
    "# class Solution:\n",
    "#     def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "#         @cache\n",
    "#         def sub(i: int, j: int, k: int) -> float:\n",
    "#             d = j - i\n",
    "#             if k == 0 or k > d:\n",
    "#                 return float('-inf') # 表示已无意义\n",
    "#             if k == d:\n",
    "#                 return sum(nums[i:j])\n",
    "#             if k == 1:\n",
    "#                 return sum(nums[i:j]) / d\n",
    "#             return max(sub(i, m, 1) + sub(m, j, k-1) for m in range(i+1, j))\n",
    "#         return sub(0, len(nums), k)\n",
    "\n",
    "# 递归（超时）\n",
    "# class Solution:\n",
    "#     def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "#         def sub(nums: List[int], k: int) -> float:\n",
    "#             if k == 0 or k > len(nums):\n",
    "#                 return float('-inf') # 表示已无意义\n",
    "#             if k == len(nums):\n",
    "#                 return sum(nums)\n",
    "#             if k == 1:\n",
    "#                 return sum(nums) / len(nums)\n",
    "#             return max(sub(nums[:i], 1) + sub(nums[i:], k-1) for i in range(1, len(nums)))\n",
    "#         return sub(nums, k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        ans = np.zeros((len(nums)+1, k+1))\n",
    "        def lsa(n, t):\n",
    "            if ans[n,t] != 0:\n",
    "                return ans[n,t]\n",
    "            if n == t:\n",
    "                ans[n,t] = np.sum(nums[:n])\n",
    "                return ans[n,t]\n",
    "            if t == 1:\n",
    "                ans[n,t] = np.mean(nums[:n])\n",
    "                return ans[n,t]\n",
    "            temp = np.zeros(n)\n",
    "            for i in range(t-1, n):\n",
    "                temp[i] = lsa(i, t-1) + np.mean(nums[i:n])\n",
    "            \n",
    "            ans[n,t] = np.max(temp)\n",
    "            return ans[n,t]\n",
    "        \n",
    "        return lsa(len(nums),k)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from numpy import mean\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        if len(nums)<=k:\n",
    "            return sum(nums)\n",
    "        dp=[[0 for i in range(k+1)] for j in range(len(nums)+1)]\n",
    "        for i in range(1,k+1):\n",
    "            dp[i][i]=sum(nums[:i])\n",
    "        for i in range(1,len(nums)+1):\n",
    "            dp[i][1]=mean(nums[0:i])\n",
    "        for j in range(2,k+1):\n",
    "            for i in range(j+1,len(nums)+1):\n",
    "                dp[i][j]=max([dp[x][j-1]+mean(nums[x:i]) for x in range(j-1,i)])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from numpy import mean\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        if len(nums)<=k:\n",
    "            return sum(nums)\n",
    "        dp=[[0 for i in range(k+1)] for j in range(len(nums)+1)]\n",
    "        for i in range(1,k+1):\n",
    "            dp[i][i]=sum(nums[:i])\n",
    "        for i in range(1,len(nums)+1):\n",
    "            dp[i][1]=mean(nums[0:i])\n",
    "        for j in range(2,k+1):\n",
    "            for i in range(j+1,len(nums)+1):\n",
    "                dp[i][j]=max([dp[x][j-1]+sum(nums[x:i])/(i-x) for x in range(j-1,i)])\n",
    "        return dp[-1][-1]\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        # @cache\n",
    "        # def dfs(i, j, p):\n",
    "        #     res = 0\n",
    "        #     if p == 1:\n",
    "        #         res = sum(nums[x] for x in range(i,j+1))/(j-i+1)\n",
    "        #     elif j-i+1 == p:\n",
    "        #         res = sum(nums[x] for x in range(i,j+1))\n",
    "        #     else:\n",
    "        #         for h in range(i, j):\n",
    "        #             if j-h < p-1:\n",
    "        #                 break\n",
    "        #             res = max(res, dfs(i,h,1) + dfs(h+1,j,p-1))\n",
    "        #     return res\n",
    "        # return dfs(0, n-1, k)\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [[[0 for _ in range(k+1)] for _ in range(n+1)] for _ in range(n+1)]\n",
    "        # for i in range(n):\n",
    "        #     dp[i][i][1] = nums[i]\n",
    "        for p in range(1, k+1):\n",
    "            for l in range(p, n+1):\n",
    "                for i in range(n):\n",
    "                    j = i+l-1\n",
    "                    if j >= n:\n",
    "                        break\n",
    "                    if l == p:\n",
    "                        dp[i][j][p] = sum(nums[x] for x in range(i,j+1))\n",
    "                    elif p == 1:\n",
    "                        dp[i][j][p] = sum(nums[x] for x in range(i,j+1))/l\n",
    "                    else:\n",
    "                        for h in range(i,j):\n",
    "                            if j-h < p-1:\n",
    "                                break\n",
    "                            dp[i][j][p] = max(dp[i][j][p], dp[i][h][1] + dp[h+1][j][p-1])\n",
    "        return dp[0][n-1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy\n",
    "\n",
    "class Solution:\n",
    "    def f(self, b, e, k):\n",
    "        assert b < e\n",
    "        if (b, e, k) in self.d:\n",
    "            return self.d[(b, e, k)]\n",
    "        if e - b == k:\n",
    "            self.d[(b, e, k)] = sum(self.nums[b: e])\n",
    "            return self.d[(b, e, k)]\n",
    "        if k == 1:\n",
    "            self.d[(b, e, k)] = numpy.average(self.nums[b:e])\n",
    "            return self.d[(b, e, k)]\n",
    "        max_score = 0\n",
    "        for i in range(b + 1, e - k + 2):\n",
    "            score1 = self.f(b, i, 1)\n",
    "            score2 = self.f(i, e, k - 1)\n",
    "            score = score1 + score2\n",
    "            max_score = max(max_score, score)\n",
    "        self.d[(b, e, k)] = max_score\n",
    "        return max_score\n",
    "\n",
    "\n",
    "\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        self.nums = nums\n",
    "        self.d = {}\n",
    "        return self.f(0, len(nums), k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        prefix = [0]*len(nums)\n",
    "        prev = 0\n",
    "        for i in range(len(nums)):\n",
    "            prev+=nums[i]\n",
    "            prefix[i]=prev\n",
    "        # @cache\n",
    "        # def dfs(i,j,k):\n",
    "        #     if i<1 or k==1:\n",
    "        #         return prefix[j]/(j+1)\n",
    "        #     res = max(dfs(i-1,i-1,k-1)+(prefix[j]-prefix[i-1])/(j-i+1),dfs(i-1,j,k))\n",
    "        #     return res\n",
    "        # return dfs(len(nums)-1,len(nums)-1,k)\n",
    "        n = len(nums)\n",
    "        dp = [[[0]*(k+1) for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i][1] = prefix[i]/(i+1)\n",
    "    \n",
    "        for i in range(1,n):\n",
    "            for j in range(i,n):\n",
    "                for k in range(2,k+1):\n",
    "                    dp[i][j][k] = max(dp[i-1][i-1][k-1]+(prefix[j]-prefix[i-1])/(j-i+1), dp[i-1][j][k]) \n",
    "        return dp[n-1][n-1][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n=len(nums)\n",
    "        # @cache\n",
    "        # def dfs(i,la,c):\n",
    "        #     if i<k-2-c:\n",
    "        #         return -inf\n",
    "        #     if c==k-1:\n",
    "        #         return s[la+1]/(la+1)\n",
    "        #     return max(dfs(i-1,i,c+1)+(s[la+1]-s[i+1])/(la-i),dfs(i-1,la,c))\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        # return dfs(n-2,n-1,0)\n",
    "        f=[[[0]*k for _ in range(n)] for _ in range(n+1)]\n",
    "        for i in range(-2,n-1):\n",
    "            for la in range(i+1,n):\n",
    "                for c in range(k):\n",
    "                    if i<k-2-c:\n",
    "                        f[i][la][c]=-inf\n",
    "                        continue\n",
    "                    if c==k-1:\n",
    "                        f[i][la][c]=s[la+1]/(la+1)\n",
    "                        continue\n",
    "                    f[i][la][c]=max(f[i-1][i][c+1]+(s[la+1]-s[i+1])/(la-i),f[i-1][la][c])\n",
    "        return f[n-2][n-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def largestSumOfAverages(self, nums: List[int], k: int) -> float:\n",
    "        n=len(nums)\n",
    "        # @cache\n",
    "        # def dfs(i,la,c):\n",
    "        #     if i<k-2-c:\n",
    "        #         return -inf\n",
    "        #     if c==k-1:\n",
    "        #         return s[la+1]/(la+1)\n",
    "        #     return max(dfs(i-1,i,c+1)+(s[la+1]-s[i+1])/(la-i),dfs(i-1,la,c))\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        # return dfs(n-2,n-1,0)\n",
    "        f=[[[0]*k for _ in range(n)] for _ in range(n+1)]\n",
    "        for i in range(-2,n-1):\n",
    "            for la in range(i+1,n):\n",
    "                for c in range(k-1,-1,-1):\n",
    "                    if i<k-2-c:\n",
    "                        f[i][la][c]=-inf\n",
    "                        continue\n",
    "                    if c==k-1:\n",
    "                        f[i][la][c]=s[la+1]/(la+1)\n",
    "                        continue\n",
    "                    f[i][la][c]=max(f[i-1][i][c+1]+(s[la+1]-s[i+1])/(la-i),f[i-1][la][c])\n",
    "        return f[n-2][n-1][0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
